lib/Minimum range query using segment trees/SegmentTree.cpp

   1 #include <vector>
   2 using namespace std;
   3
   4 class SegmentTree{
   5 public:
   6   vector<int> arr, tree;
   7   int n;
   8
   9   SegmentTree(){}
  10   SegmentTree(const vector<int> &arr) : arr(arr) {
  11     initialize();
  12   }
  13
  14   //must be called after assigning a new arr.
  15   void initialize(){
  16     n = arr.size();
  17     tree.resize(4*n + 1);
  18     initialize(0, 0, n-1);
  19   }
  20
  21   int query(int query_left, int query_right) const{
  22     return query(0, 0, n-1, query_left, query_right);
  23   }
  24
  25   void update(int where, int what){
  26     update(0, 0, n-1, where, what);
  27   }
  28
  29 private:
  30   int initialize(int node, int node_left, int node_right);
  31   int query(int node, int node_left, int node_right, int query_left, int query_right) const;
  32   void update(int node, int node_left, int node_right, int where, int what);
  33 };
  34
  35 int SegmentTree::initialize(int node, int node_left, int node_right){
  36   if (node_left == node_right){
  37     tree[node] = node_left;
  38     return tree[node];
  39   }
  40   int half = (node_left + node_right) / 2;
  41   int ans_left = initialize(2*node+1, node_left, half);
  42   int ans_right = initialize(2*node+2, half+1, node_right);
  43
  44   if (arr[ans_left] <= arr[ans_right]){
  45     tree[node] = ans_left;
  46   }else{
  47     tree[node] = ans_right;
  48   }
  49   return tree[node];
  50 }
  51
  52 int SegmentTree::query(int node, int node_left, int node_right, int query_left, int query_right) const{
  53   if (node_right < query_left || query_right < node_left) return -1;
  54   if (query_left <= node_left && node_right <= query_right) return tree[node];
  55
  56   int half = (node_left + node_right) / 2;
  57   int ans_left = query(2*node+1, node_left, half, query_left, query_right);
  58   int ans_right = query(2*node+2, half+1, node_right, query_left, query_right);
  59
  60   if (ans_left == -1) return ans_right;
  61   if (ans_right == -1) return ans_left;
  62
  63   return (arr[ans_left] <= arr[ans_right] ? ans_left : ans_right);
  64 }
  65
  66 void SegmentTree::update(int node, int node_left, int node_right, int where, int what){
  67   if (where < node_left || node_right < where) return;
  68   if (node_left == where && where == node_right){
  69     arr[where] = what;
  70     tree[node] = where;
  71     return;
  72   }
  73   int half = (node_left + node_right) / 2;
  74   if (where <= half){
  75     update(2*node+1, node_left, half, where, what);
  76   }else{
  77     update(2*node+2, half+1, node_right, where, what);
  78   }
  79   if (arr[tree[2*node+1]] <= arr[tree[2*node+2]]){
  80     tree[node] = tree[2*node+1];
  81   }else{
  82     tree[node] = tree[2*node+2];
  83   }
  84 }